package linkedlist;

import java.util.HashSet;
import java.util.Set;

/**
 * 判断链表是否有环
 */
public class LinkedListCycle {

  /**
   * 采用快慢指针，快指针每次走两步，慢指针每次走一步，如果快慢指针能相遇，则说明有环
   *
   * @param head
   * @return true:有环, false:无环
   */
  public boolean hasCycle(ListNode head) {
    if (head == null || head.next == null) {
      return false;
    }
    ListNode quick = head.next.next, slow = head.next;
    while (quick != slow) {
      if (quick == null || quick.next == null) {
        return false;
      }
      quick = quick.next.next;
      slow = slow.next;
    }
    return true;
  }

  /**
   * 暴力法。循环Integer.MAX_VALUE / 30次，若能发现null，则说明无环，在给定次数内，都没发现null，
   * 则认为是有环的。【该方法不一定准确】
   *
   * @param head
   * @return
   */
  public boolean hasCycle2(ListNode head) {
    ListNode cur = head;
    for (int i = 0; i < Integer.MAX_VALUE / 30; ++i) {
      if (cur == null || cur.next == null) {
        return false;
      }
      cur = cur.next;
    }
    return true;
  }

  /**
   * 使用Set将遍历过的节点保存下来，每次走到新的节点时先查询Set中是否存在该节点，若存在，说明有环
   *
   * @param head
   * @return
   */
  public boolean hasCycle3(ListNode head) {
    Set<ListNode> visited = new HashSet<>();
    ListNode cur = head;
    while (true) {
      if (cur == null) {
        return false;
      }
      if (visited.contains(cur)) {
        return true;
      }
      visited.add(cur);
      cur = cur.next;
    }
  }
}
